Numerous cryptographic algorithms are based on exponentiation calculations of the type y=xr, where x is an element of an assembly noted in a multiplicative manner and r a predetermined number, which encode a value y. This is particularly the case with the RSA (Rivest, Shamir and Adleman) algorithm. The value y may correspond for example to an encrypted text or to a signed or verified datum.
Various types of exponentiation algorithms exist. The “square and multiply” (SAM) binary method, the Yacobi method, known as MM3 or the sliding windows method are known in particular.
Said algorithms must include suitable counter-measures against attacks aiming to discover the information contained and manipulated in the processes carried out by the calculation device.
In particular, counter-measures are provided against so-called simple or differential hidden channel attacks. Simple or differential hidden channel attack is understood to mean an attack based on a physical magnitude that can be measured from outside the device, and the direct analysis (simple attack) or analysis according to a statistical method (differential attack) make it possible to discover the information contained and manipulated in the processes carried out. Said attacks thus make it possible to discover confidential information. Said attacks have in particular been disclosed by Paul Kocher (Advances in Cryptology—CRYPTO '99, vol. 1666 of Lecture Notes in Computer Science, pp. 388-397. Springer-Verlag, 1999). Among the physical magnitudes which can be exploited for this purpose are current consumption, electromagnetic field, etc. Said attacks are based on the fact that the manipulation of a bit, i.e. the processing thereof by a specific instruction has a particular imprint on the physical magnitude considered according to its value.
The aforementioned exponentiation algorithms have had to include counter-measures for preventing said attacks from succeeding.
An effective counter-measure to differential attacks is to make random the inputs and/or outputs of the exponentiation algorithm used for calculating y=xr. In other words, it involves making the operand x and/or the exponent r random.
Concerning the simple attacks, it is known to secure said algorithms by eliminating all of the connections conditional to the value of the datum processed or the connections via which a different operation is executed.
If the example of the method the most commonly used in public key cryptographic systems is taken, the binary method, also designated by the SAM (for “square and multiply”) method, two variants of implementation exist, depending on whether the bits of the number r are scanned from right to left or from left to right.
In the first case, for a right to left scanning, the SAM algorithm can be written in the following manner:
Inputs of the algorithm: x, r=(rm−1, rm−2,..., r0) in base 2.Outputs of the algorithm: y=xr.Temporary registers used: R0, R1.Initialisation: R0<−1 (neutral element of themultiplication); R1<−x.For i=0 to m−1, carry out:If ri=1, then R0<−R0.R1R1<−(R1)2End forReturn R0.
In the second case, for a left to right scanning, the SAM algorithm can be written in the following manner:
Inputs of the algorithm: x, r=(rm−1, rm−2, ..., r−2) in base 2.Outputs of the algorithm: y=xr.Temporary registers used: R0.Initialisation: R0<−1 (neutral element of themultiplication);For i=m−1 to 0, carry out:R0<−(R0)2If ri=1, then R0<−R0.xEnd forReturn R0.
However, said algorithms have the disadvantage of implementing a condition on the value of the bits ri, which makes same sensitive to hidden channel attacks.
To secure said algorithms in relation to simple hidden channel attacks, the method generally used is to eliminate the connections conditional to the value of the number r (the secret key), such that a constant code algorithm is obtained. The secured binary method, thus becomes the so-called “square and multiply always” method, or SMA algorithm, i.e. a method wherein a multiplication and an elevation to the square are carried out systematically.
In the case of a left to right scanning, the secured SMA algorithm can be written as follows:
Inputs of the algorithm: x, r=(rm−1, rm−2, ..., r0) in base 2.Outputs of the algorithm: y=xr.Temporary registers used: R0, R1Variable used: bInitialisation: R0<−1 (neutral element of themultiplication);For i=m−1 to 0, carry out:R0<−(R0)2b=1−r1;Rb<−R0.xEnd forReturn R0.
In said algorithm, a useless multiplication is carried out, when the bit ri of the number r equals 0. The performances of the resulting secured algorithm in terms of number of multiplications to be carried out are therefore reduced.
Generally, the securing of exponentiation algorithms by adding dummy operations in relation to simple attacks affects the performances of said algorithms in a significant manner.
Moreover, algorithms including dummy operations are sensitive to safe-error attacks. Indeed, by injecting a fault at a precise moment during the calculations, it is possible to detect if an operation is dummy or not, and in this way to deduce a secret. Said type of “safe-error” attack has, for example, been described in the publication by MM Yen and Joye “Checking before output may not be enough against fault based cryptanalysis” in the IEEE journal “Transactions on Computers”, 49(9):967-970, 2000.
Finally, it must be understood for the purposes of the application that exponentiation calculations in multiplicative groups are equivalent to multiplications by a scalar in additively denoted groups. In the rest of the present application, and without indication to the contrary, an additive notation will be used, such as used for example in elliptical curves. Said notation must in no circumstances be considered as a limitation to the invention.